package leetcode.图.拓扑排序;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/7 21:16
 * @description：https://leetcode-cn.com/problems/course-schedule-iv/
 */
public class 课程表IV {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.checkIfPrerequisite(5,
                new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}},
                new int[][]{{0, 4}, {4, 0}, {1, 3}, {3, 0}}));
    }


    class Solution {
        //floyed算法
        public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
            boolean[][] floyed = new boolean[numCourses][numCourses];
            for (int[] prerequisite : prerequisites) {
                floyed[prerequisite[0]][prerequisite[1]] = true;
            }

            for (int k = 0; k < numCourses; k++) {
                for (int i = 0; i < numCourses; i++) {
                    for (int j = 0; j < numCourses; j++) {
                        floyed[i][j] = floyed[i][j] || (floyed[i][k] && floyed[k][j]);
                    }
                }
            }

            ArrayList<Boolean> ans = new ArrayList<>();
            for (int[] query : queries) {
                ans.add(floyed[query[0]][query[1]]);
            }
            return ans;
        }
    }
}
